package com.fmm.medium;

public class SumGame {

    /**
     * 先手：尝试把 ? 填入数字，使得前半部分之和 和 后半部分之和不相等
     * 后手：尝试把 ? 填入数字，使得前半部分之和 和 后半部分之相等
     * 先后手交替填数字，直到填完所有 ?
     * num 的前半部分之和 和 后半部分之和不相等，则返回 true，否则返回 false
     *
     * @param num 一串可能包含 ? 的数字串
     * @return 如果 num 的前半部分之和 和 后半部分之和不相等，则返回 true，否则返回 false
     */
    public static boolean sumGame(String num) {
        int length = num.length();
        // 前半部分数字总和
        int leftSum = 0;
        // 后半部分数字总和
        int rightSum = 0;
        // 前半部分 ? 的个数
        int leftQuestionMark = 0;
        // 后半部分 ? 的个数
        int rightQuestionMark = 0;
        for (int i = 0; i < length / 2; i++) {
            if (num.charAt(i) == '?') {
                leftQuestionMark++;
            } else {
                leftSum += num.charAt(i) - '0';
            }
            if (num.charAt(length - 1 - i) == '?') {
                rightQuestionMark++;
            } else {
                rightSum += num.charAt(length - 1 - i) - '0';
            }
        }

        // 整个 num 中没有 ?
        if (leftQuestionMark == 0 && rightQuestionMark == 0) {
            return leftSum != rightSum;
        }

        // 整个 num 中有奇数个 ?
        if ((leftQuestionMark + rightQuestionMark)%2 == 1) {
            return true;
        }

        // 整个 num 中有偶数个 ?
        // y-x = (m-n)/2 * 9
        if (leftQuestionMark >= rightQuestionMark) {
            return (rightSum - leftSum) != (leftQuestionMark - rightQuestionMark) / 2 * 9;
        } else {
            return (leftSum - rightSum) != (rightQuestionMark - leftQuestionMark) / 2 * 9;
        }
    }

    public static void main(String[] args) {
        System.out.println(sumGame("8?6?90?5"));
    }
}
